package cn.edu.xjtu.work.twoSum;

/**
 * 1. 两数之和
 * 
 * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
 * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。
 */

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Solution {
  public static void main(String[] args) {
    // int[] nums = { 3, 5, 12, 6, 23, 6, 12 };
    // int[] nums = { 3, 3 };
    // int[] nums = { -3, 4, 3, 90 };
    int[] nums = { -18, 12, 3, 0 };
    twoSum(nums, -6);
  }

  /**
   * 哈希表
   * 
   * @param nums
   * @param target
   * @return
   */
  public static int[] twoSum2(int[] nums, int target) {
    Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
    for (int i = 0; i < nums.length; i++) {
      if (hashtable.containsKey(target - nums[i])) {
        return new int[] { hashtable.get(target - nums[i]), i };
      }
      hashtable.put(nums[i], i);
    }
    return new int[0];
  }

  /**
   * 排序加双指针
   * 
   * @param nums
   * @param target
   * @return
   */
  public static int[] twoSum(int[] nums, int target) {
    int[] ret = new int[2];
    int[] arr = nums.clone();
    Arrays.sort(arr);
    int index = -1;
    // System.out.println("nums " + Arrays.toString(nums));
    // System.out.println("arr " + Arrays.toString(arr));
    // 找到比target小的最大元素下标
    for (int i = 0; i < arr.length; i++) {
      if (arr[i] + arr[0] > target) {
        break;
      }
      index = i;
    }
    int left = 0;
    int right = arr.length - 1;
    if (index == -1) {
      return null;
    } else {
      while (left != right) {
        if (arr[left] + arr[right] == target) {
          ret[0] = arr[left];
          ret[1] = arr[right];
          break;
        } else if (arr[left] + arr[right] > target) {
          right--;
        } else {
          left++;
        }
      }
      // System.out.println(left + "" + right);
      boolean leftFlag = true;
      boolean rightFlag = true;

      for (int i = 0; i < nums.length; i++) {
        if (nums[i] == ret[0] && leftFlag) {
          ret[0] = i;
          leftFlag = false;
        } else if (nums[i] == ret[1] && rightFlag) {
          ret[1] = i;
          rightFlag = false;
        }
      }
      // System.out.println(Arrays.toString(ret));
      return ret;
    }
  }

}
